package com.tgy.algorithm._经典题目01;

/**
 * 给定一个只由 0(假)、1(真)、&(逻辑与)、|(逻辑或)和^(异或)五种字符组成 的字符串express，
 * 再给定一个布尔值 desired。返回express能有多少种组合 方式，可以达到desired的结果，
 * 【举例】
 * express="1^0|0|1"，desired=false 只有 1^((0|0)|1)和 1^(0|(0|1))的组合可以得到 false，返回 2。
 *
 * express=”1" desired=false 无组合则可以得到false，返回0
 */
public class _032_01与非异或组合 {

    public static boolean check(String patter) {

        int len = patter.length();

        if ((len & 1) == 0) {
            return false;
        }

        char[] chars = patter.toCharArray();
        for (int i = 0; i < len; i+=2) {
            char c = chars[i];
            if (c != '1' && c != '0') {
                return false;
            }
        }

        for (int i = 1; i < len; i += 2) {
            if (chars[i] != '|' && chars[i] != '^' && chars[i] != '&') {
                return false;
            }
        }

        return true;
    }

    public static int findNums(String patter,boolean desired) {

        if (patter == null || patter.length() == 0) {
            return 0;
        }

        if (!check(patter)) {
            return 0;
        }

        char[] chars = patter.toCharArray();
        int counts = doFindNums(chars, 0, chars.length - 1, desired);
        return counts;
    }

    public static int doFindNums(char[] chars, int left,int right,boolean desired) {

        if (left == right) {
            if (desired) {
                return chars[left] == '1' ? 1:0;
            }else {
                return chars[left] == '0' ? 1:0;
            }
        }

        int count = 0;
        if (desired) {
            for (int i = left + 1; i <= right ; i+= 2) {
                if (chars[i] == '|') {
                    count += doFindNums(chars, left,i - 1,true) * doFindNums(chars,i + 1,right,true);
                    count += doFindNums(chars, left,i - 1,true) * doFindNums(chars,i + 1,right,false);
                    count += doFindNums(chars, left,i - 1,false) * doFindNums(chars,i + 1,right,true);
                }else if(chars[i] == '&') {
                    count += doFindNums(chars, left,i - 1,true) * doFindNums(chars,i + 1,right,true);
                }else if(chars[i] == '^') {
                    count += doFindNums(chars, left,i - 1,true) * doFindNums(chars,i + 1,right,false);
                    count += doFindNums(chars, left,i - 1,false) * doFindNums(chars,i + 1,right,true);
                }
            }
        }else {
            for (int i = left + 1; i <= right ; i+= 2) {
                if (chars[i] == '|') {
                    count += doFindNums(chars, left,i - 1,false) * doFindNums(chars,i + 1,right,false);
                }else if(chars[i] == '&') {
                    count += doFindNums(chars, left,i - 1,false) * doFindNums(chars,i + 1,right,false);
                    count += doFindNums(chars, left,i - 1,true) * doFindNums(chars,i + 1,right,false);
                    count += doFindNums(chars, left,i - 1,false) * doFindNums(chars,i + 1,right,true);
                }else if(chars[i] == '^') {
                    count += doFindNums(chars, left,i - 1,true) * doFindNums(chars,i + 1,right,true);
                    count += doFindNums(chars, left,i - 1,false) * doFindNums(chars,i + 1,right,false);
                }
            }
        }

        return count;
    }

    public static int findNums01(String pattern, boolean desired) {

        if (pattern == null || pattern.length() == 0) {
            return 0;
        }

        if (!check(pattern)) {
            return 0;
        }

        int len = pattern.length();

        char[] chars = pattern.toCharArray();

        int[][] cacheT = new int[len][len];
        int[][] cacheF = new int[len][len];

        for (int i = 0; i < len; i+= 2) {
           if (chars[i] == '1') {
               cacheT[i][i] = 1;
           }

           if(chars[i] == '0') {
               cacheF[i][i] = 1;
           }
        }

        int countF = 0;
        int countT = 0;

        for (int i = len - 3; i >= 0; i -= 2) {
            for (int j = i + 2; j < len; j += 2) {
                //  [i,j]
                countF = 0;
                countT = 0;
                for (int k = i + 1; k < j; k += 2) {
                    char ch = chars[k];
                    if (ch == '|') {
                        // true
//                        countF += doFindNums(chars, left,i - 1,true) * doFindNums(chars,i + 1,right,true);
                        countT += (cacheT[i][k - 1] * cacheT[k+1][j]);
//                        countF += doFindNums(chars, left,i - 1,true) * doFindNums(chars,i + 1,right,false);
                        countT += (cacheT[i][k-1] * cacheF[k+1][j]);
//                        countF += doFindNums(chars, left,i - 1,false) * doFindNums(chars,i + 1,right,true);
                        countT += (cacheF[i][k-1] * cacheT[k+1][j]);
                    }else if(ch == '&') {
//                      true
//                        countF += doFindNums(chars, left,i - 1,true) * doFindNums(chars,i + 1,right,true);
                        countT += (cacheT[i][k - 1] * cacheT[k+1][j]);
                    }else if(ch == '^') {
//                        true
//                        countF += doFindNums(chars, left,i - 1,true) * doFindNums(chars,i + 1,right,false);
                        countT += (cacheT[i][k - 1] * cacheF[k+1][j]);
//                        countF += doFindNums(chars, left,i - 1,false) * doFindNums(chars,i + 1,right,true);
                        countT += (cacheF[i][k  - 1] * cacheT[k+1][j]);
                    }
                }

                for (int k = i + 1; k < j; k += 2) {
                    char ch = chars[k];
                    if (ch == '|') {
                        // false
//                        count += doFindNums(chars, left,i - 1,false) * doFindNums(chars,i + 1,right,false);
                        countF += (cacheF[i][k - 1] * cacheF[k + 1][j]);
                    }else if(ch == '&') {
                        // false
//                        count += doFindNums(chars, left,i - 1,false) * doFindNums(chars,i + 1,right,false);
                        countF += (cacheF[i][k -  1] * cacheF[k + 1][j]);
//                        count += doFindNums(chars, left,i - 1,true) * doFindNums(chars,i + 1,right,false);
                        countF += (cacheT[i][k - 1] * cacheF[k+1][j]);
//                        count += doFindNums(chars, left,i - 1,false) * doFindNums(chars,i + 1,right,true);
                        countF += (cacheF[i][k - 1] * cacheT[k+1][j]);
                    }else if(ch == '^') {
                        // false
//                        count += doFindNums(chars, left,i - 1,true) * doFindNums(chars,i + 1,right,true);
                        countF += (cacheT[i][k - 1] * cacheT[k+1][j]);
//                        count += doFindNums(chars, left,i - 1,false) * doFindNums(chars,i + 1,right,false);
                        countF += (cacheF[i][k -  1] * cacheF[k + 1][j]);
                    }
                }
                cacheT[i][j] = countT;
                cacheF[i][j] = countF;
            }
        }

        return desired ? cacheT[0][len - 1] : cacheF[0][len - 1];
    }

    public static void main(String[] args) {
        String express="1^0|0|1";
//        int nums = findNums(express, false);
        int nums = findNums01(express, false);
        System.out.println(nums);
    }
}
